package CommonAlgs.DP;

/**
 * @Author ChanZany
 * @Date 2021/5/14 20:49
 * @Version 1.0
 * <p>
 * <p>
 * w:物品重量
 * v:物品价值
 * 构建dp矩阵f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]),其中
 * i:可选物品数量
 * j:背包容量
 */
public class ZeroOnePackage {
    public static void main(String[] args) {
        int itemNum=4,packetSize=8;
        int[][] f = new int[itemNum+1][packetSize+1];
        int[] w = {0, 2, 3, 4, 5};
        int[] v = {0, 3, 4, 5, 8};
        int res = solution(w,v,f,itemNum,packetSize);
        System.out.println(res);
    }

    private static int solution(int[] w, int[] v, int[][] f, int itemNum, int packetSize) {
        for (int i = 1; i < itemNum+1; i++) { //i表示可选物品数量
            for (int j = 1; j < packetSize+1; j++) { //j表示剩余背包容量
                if (w[i]>j){
                    f[i][j]=f[i-1][j]; //无法偷取
                }
                else{
                    f[i][j] = Math.max(
                            f[i-1][j-w[i]]+v[i], //偷
                            f[i-1][j] //不偷
                    );
                }

            }
        }
        for (int i = 0; i < itemNum + 1; i++) {
            for (int j = 0; j < packetSize + 1; j++) {
                System.out.printf("f[%d][%d]=%d\n",i,j,f[i][j]);
            }
        }
        return f[itemNum][packetSize];
    }
}
